package com.hh.demo;

import java.util.Random;
import java.util.Scanner;

import javax.swing.JOptionPane;
public class                          Linearselect {
    public Linearselect() {
        Scanner sc=new Scanner(System.in);
        int k,n,i;
        System.out.println("问题一：2-9线性时间选择问题");
        //System.out.println("请输入数组的大小：");
        n=Integer.parseInt(JOptionPane.showInputDialog("请输入数组的大小："));
        //n=sc.nextInt();
        int []a=new int[n];
        //System.out.println("请输入数组的各个元素：");
        for(i=0;i<n;i++)
        {
            //a[i]=sc.nextInt();
            a[i]=Integer.parseInt(JOptionPane.showInputDialog("请输入数组的第"+(i+1)+"个元素："));
        }
        //System.out.println("请输入要查找的第k小数：");
        //k=sc.nextInt();
        k=Integer.parseInt(JOptionPane.showInputDialog("请输入要查找的第k小数："));
        int result,p=0;
        result=randomizedSelect(a, p, n-1, k);
        String s="数组为：";
        System.out.print("数组为：");
        for(i=0;i<n;i++) {
            System.out.print(a[i]+" ");
            s=s+a[i]+" ";
        }
        System.out.println("\n查找的第"+k+"小数为："+result);
        String title="线性时间选择算法输出";
        JOptionPane.showMessageDialog(null,s+"\n查找的第"+k+"小数为："+result,title,JOptionPane.INFORMATION_MESSAGE);
        sc.close();
    }
    public static int randomizedPartition(int[] a,int p,int r){
        int i=random(p,r);
        swap(a,i,p);//交换枢纽元素到区间左端
        return partition(a,p,r);
    }
    /**
     * 线性选择指定数组中第k小的元素
     * @param a 指定数组
     * @param p 区间左端
     * @param r 区间右端
     * @param k 数组的大小位置
     * @return 返回指定数组中第k小的元素
     **/
    public static int randomizedSelect(int[] a,int p,int r,int k){
        if(p==r) {
            return a[p];
        }
        int i=randomizedPartition(a,p,r);
        int j=i-p+1;//左端元素个数
        //第k小的元素在左端
        if(k<=j) {
            return randomizedSelect(a,p,i,k);
        } else//第k小的元素在右端，并且左端已经有j个比它小的元素
            //所以只要找右端中的第k-j小的元素就可以
        {
            return randomizedSelect(a,i+1,r,k-j);
        }
    }
    public static int random(int i,int j){
        Random r=new Random();
        return r.nextInt(j-i)+i;
    }
    public static int partition(int[] a,int p,int r){
        int i=p,j=r+1;
        int x=a[p];
        while(true){
            while(a[++i]<x&&i<r) {
                ;
            }
            while(a[--j]>x) {
                ;
            }
            if(i>=j) {
                break;
            }
            swap(a,i,j);
        }
        a[p]=a[j];
        a[j]=x;
        return j;
    }
    public static void swap(int[] a,int i,int j){
        int temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }
}


